class Treenode:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = 0


class Solution(object):
    def longestWord(self, words):
        words.sort(key=lambda x: len(x))
        tree = Treenode('#')
        max_word = ''
        for word in words:
            node = tree
            flag = True
            for index, w in enumerate(word):
                if w in node.neighbors:
                    node = node.neighbors[w]
                    if not node.flag:
                        flag = False
                else:
                    new_node = Treenode(w)
                    node.neighbors[w] = new_node
                    node = new_node
                    if index != len(word) - 1:
                        flag = False
            node.flag = 1
            if flag:
                if not max_word:
                    max_word = word
                else:
                    if len(word) > len(max_word):
                        max_word = word
                    else:
                        if len(word) == len(max_word):
                            max_word = min(max_word, word)
        return max_word


data = Solution()
words = ["k", "ki", "kir", "kira", "kiran"]
print(data.longestWord(words))
